package com.dyz.leetcode._18_backtracking;

import java.util.*;

public class _301_removeInvalidParentheses {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> set = new HashSet<>();
        queue.add(s);
        set.add(s);
        boolean findFlag = false;
        while (!queue.isEmpty()){
            int size = queue.size();
            for(int i =0; i<size; i++){
                String currStr = queue.poll();
                if(isValid(currStr)){
                    res.add(currStr);
                    findFlag = true;
                }
                if(findFlag){continue;}
                int currStrLen = currStr.length();
                for (int j=0; j<currStrLen; j++){
                    if(currStr.charAt(j)!='(' && currStr.charAt(j)!=')'){continue;}
                    String leftStr =  currStr.substring(0, j);
                    String rightStr = (j==currStrLen-1)?"":currStr.substring(j+1, currStrLen);
                    String nextStr = leftStr+rightStr;
                    if(!set.contains(nextStr)){
                        queue.add(nextStr);
                        set.add(nextStr);
                    }
                }
            }
            if(findFlag){break;}
        }
        return res;
    }
    private boolean isValid(String s){
        int count = 0;
        for(char c: s.toCharArray()){
            if(c=='('){ count++;}
            else if(c==')'){count--;}
            if (count < 0) {return false;}
        }
        return count == 0;
    }
}
